/**
 * @file ChildRepresentation.c
 * @desc 使用「孩子表示法」实现树的存储结构与基本操作，包括初始化、创建示例树、打印树及释放内存功能。
 * @author WangBlue (wangjiping596@gmail.com)
 * @date 2025/10/17 11:00
 * @version 1.0
 */

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 10  ///< 树中最大节点数

/**
 * @struct childNode
 * @brief 孩子链表节点
 *
 * @var data 孩子节点在 tree 节点数组中的下标
 * @var next 指向下一个孩子节点
 */
typedef struct childNode {
    int data;
    struct childNode *next;
} childNode;

/**
 * @struct treeNode
 * @brief 树节点（孩子表示法）
 *
 * @var data 节点存储的数据（字符类型）
 * @var firstChild 指向该节点孩子链表的头指针
 */
typedef struct treeNode {
    char data;
    struct childNode *firstChild;
} treeNode;

/**
 * @struct tree
 * @brief 孩子表示法树结构
 *
 * @var nodes 树中所有节点数组
 * @var count 当前树中节点的数量
 */
typedef struct tree {
    treeNode nodes[MAX_SIZE];
    int count;
} tree;

/**
 * @brief 初始化树结构
 * @param t 指向待初始化树结构的指针
 *
 * @note
 * 初始化后：
 * - count = 0
 * - 每个节点的 firstChild 置为 NULL
 */
void initTree(tree *t) {
    t->count = 0;
    for (int i = 0; i < MAX_SIZE; i++) {
        t->nodes[i].firstChild = NULL;
    }
}

/**
 * @brief 创建一个孩子链表节点
 * @param data 孩子节点对应 tree 节点数组的下标
 * @return 返回新建孩子节点指针
 */
childNode* createChildNode(int data) {
    childNode* newNode = (childNode*) malloc(sizeof(childNode));
    if (!newNode) return NULL;
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

/**
 * @brief 创建一棵示例树
 *
 * 树的逻辑结构：
 * ```
 *        A
 *      / | \
 *     B  C  D
 *        / \
 *       E   F
 * ```
 * - 节点 A 的孩子链表：B(1) → C(2) → D(3)
 * - 节点 C 的孩子链表：E(4) → F(5)
 *
 * @param t 指向待创建的树结构
 */
void createSimpleTree(tree *t) {
    initTree(t);
    t->count = 6;

    // 初始化节点数据
    t->nodes[0].data = 'A';
    t->nodes[1].data = 'B';
    t->nodes[2].data = 'C';
    t->nodes[3].data = 'D';
    t->nodes[4].data = 'E';
    t->nodes[5].data = 'F';

    // 建立孩子链表
    t->nodes[0].firstChild = createChildNode(1);
    t->nodes[0].firstChild->next = createChildNode(2);
    t->nodes[0].firstChild->next->next = createChildNode(3);

    t->nodes[2].firstChild = createChildNode(4);
    t->nodes[2].firstChild->next = createChildNode(5);
}

/**
 * @brief 打印树结构（孩子表示法）
 * @param T 指向待打印的树
 *
 * @note
 * 输出格式：
 * ```
 * 结点    孩子链表(下标)
 * A       1(B) 2(C) 3(D)
 * C       4(E) 5(F)
 * ```
 */
void printTree(tree* T) {
    printf("结点\t孩子链表(下标)\n");
    printf("-----------------------\n");
    for (int i = 0; i < T->count; i++) {
        printf("%c\t", T->nodes[i].data);
        childNode* p = T->nodes[i].firstChild;
        while (p) {
            printf("%d(%c) ", p->data, T->nodes[p->data].data);
            p = p->next;
        }
        printf("\n");
    }
}

/**
 * @brief 释放树的孩子链表内存
 * @param t 指向待释放的树结构
 *
 * @note
 * 仅释放孩子链表节点，tree 节点数组本身不释放。
 */
void freeTree(tree *t) {
    if (t == NULL) return;
    for (int i = 0; i < MAX_SIZE; i++) {
        childNode* p = t->nodes[i].firstChild;
        while (p) {
            childNode* temp = p;
            p = p->next;
            free(temp);
        }
        t->nodes[i].firstChild = NULL; // 清空指针
    }
}

/**
 * @brief 主函数：测试孩子表示法树
 */
int main() {
    tree T;

    // 创建示例树
    createSimpleTree(&T);

    // 打印树
    printTree(&T);

    // 释放内存
    freeTree(&T);

    return 0;
}
